Multi-hop cellular networks typically rely on a set of base stations connected to a backbone network, as in conventional cellular networks, and the mechanisms of “ad hoc” networks, in which packets are relayed hop by hop between peer devices.
The expected benefits of such an approach with respect to conventional cellular networks are multifold. First, the energy consumption of mobile devices can be reduced. Indeed, the energy consumption required for radio transmission grows super-linearly with the distance at which the signal can be received. Therefore, the battery life of mobile devices can be substantially extended if packets are routed in small hops from the originator to the base station. Second, as an immediate positive side-effect of the reduced transmission energy, interference is reduced. Third, if not too remote from each other, mobile devices can communicate independently from the base station infrastructure. Fourth, the number of fixed antennas can be reduced. Fifth and finally, the coverage of the network can be increased using such an approach. However, while all participating mobile devices stand to benefit from such a scheme, a cheater could benefit even more, by requesting others to forward his or her packets, but avoiding the transmission of packets for other users.
Although attractive at first sight, multi-hop cellular networks raise a number of problems. For example, in conventional cellular networks, base stations usually are in charge of channel allocation and of the synchronization and power control of mobile devices. To accomplish this task, they take advantage of their direct communication link with each and every mobile device currently visiting their cell. It is quite difficult to extend these operating principles to multi-hop cellular networks. A similar observation can be made in the framework of wireless LANs. For example, in an IEEE 802.11 network, a station can work either in infrastructure mode, with one or several access points, or in ad hoc mode, but not in both.
Recently, attempts have been made to address the problem of fostering cooperation, especially for packet forwarding, in mobile ad hoc networks. For example, in S. Marti et al., “Mitigating Routing Misbehavior in Mobile Ad Hoc Networks,” Proc. Sixth ACM International Conference on Mobile Networking and Computing, Boston, August 2000 (Mobicom 2000), the authors consider the case in which some malicious nodes agree to forward packets but fail to do so. In order to cope with this problem, they propose two mechanisms: a watchdog, in charge of identifying the misbehaving nodes, and a path rater, in charge of defining the best route circumventing these nodes. Unfortunately, this scheme has the drawback that it does not discourage misbehavior.
Another proposal, described in S. Buchegger et al., “Performance Analysis of the CONFIDANT Protocol (Cooperation of Nodes: Fairness in Dynamic Ad-hoc NeTworks),” Proc. Third ACM International Symposium on Mobile Ad Hoc Networking and Computing, Lausanne, June 2002 (MobiHoc 2002), leverages on the reputation of a given user, based on the level of cooperation that user has exhibited so far. In this scheme, users can retaliate against a selfish user by denying service to the selfish user. A drawback of this type of solution is that a set of colluding cheaters can give each other large quantities of positive feedback, while giving anybody criticizing a member of the collusion negative feedback, both as a deterrent and as a way to reduce the credibility of the feedback the honest user gave.
Yet another conventional approach is described in S. Zhong et al., “Sprite: A Simple, Cheat-proof, Credit-based System for Mobile Ad Hoc Networks,” Technical Report Yale/DCS/TR1235, Department of Computer Science, Yale University, July 2002. A problem with the Sprite approach is that it does not address the case of multi-hop cellular communications. Also, although Sprite avoids assumptions on tamperproofness while still proving security statements for a stated model, it has potential drawbacks in terms of its overhead, security, and topology requirements. In particular, the Sprite approach requires a fair amount of computation and storage, making it vulnerable to denial of service attacks, and unsuitable for use in a “lightweight” device, i.e., a device having limited processing power, memory or other computational resources. Moreover, it does not consider attacks involving manipulation of routing tables. Finally, the Sprite approach is based on a reputation mechanism that will only be meaningful in rather dense networks, but it is not clear that a typical practical multi-hop cellular network exhibits this property.
A further approach is described in L. Buttyan et al., “Stimulating Cooperation in Self-Organizing Mobile Ad Hoc Networks,” ACM Journal for Mobile Networks (MONET), special issue on Mobile Ad Hoc Networks, October 2003, Vol. 8, No. 5. However, this approach relies on tamperproof hardware, and is vulnerable to collusion.
Accordingly, improved techniques are needed for encouraging collaboration between users in multi-hop cellular networks.